package com.up.interview.dataStructuresAndAlgorithms.daydayup;

import lombok.Data;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author: liuchengjun
 * @title: up20251029
 * @projectName: 海联技术中台V2.0
 * @depart 软件事业部
 * @description:
 * @date: 2025/10/29/周三 9:43 (星期三)
 * @since V2.0
 */
public class Up20251029 {

    public static void main(String[] args) {
        Up20251029 up20251029 = new Up20251029();
        List<CustomNode> input = new ArrayList<>();
        input.add(new CustomNode("A", "-1"));      // 根节点
        input.add(new CustomNode("A-1", "A"));
        input.add(new CustomNode("A-2", "A"));
        input.add(new CustomNode("A-3", "A"));
        input.add(new CustomNode("A-2-1", "A-2"));
        input.add(new CustomNode("A-2-2", "A-2"));
        input.add(new CustomNode("A-2-3", "A-2"));
        input.add(new CustomNode("A-2-4", "A-2"));
        List<String> dfs = new ArrayList<>();
//        dfs = up20251029.dfs(input);
        System.out.println(dfs);

        //方法二
        Map<String, String> map = input.stream().collect(Collectors.toMap(e -> e.id, e -> e.pid));
        for (String key : map.keySet()) {
            up20251029.digui(map,dfs,key,"");
        }
        System.out.println(dfs);
    }


    public void digui(Map<String, String> map,List<String> dfs,String cur,String pre){
        if(cur.equals("-1")){
            dfs.add(pre);
            return;
        }
        digui(map,dfs,map.get(cur),cur+"/"+pre);
    }


    /**
     * 数据库数据
     * A  -1
     * A-1  A
     * A-2  A
     * A-3  A
     * A-2-1  A-2
     * A-2-2  A-2
     * A-2-3  A-2
     * A-2-4  A-2
     * 需求：打印所有路径   A  A/A-1  A/A-2   A/A-3    A/A-2/A-2-1
     *
     * 思路1：dfs 需要知道父节点与子节点的关系   从根节点出发
     *    - 递归  递归结束条件   递归体  数据传递
     *
     *  思路二：简历map索引  子-父  从某一节点触发
     *  递归：
     *  - 遇到-1既结束并打印当前字符串
     *  - 参数传递+递归父节点
     */
    @Data
    public static class CustomNode{
        private String id;
        private String pid;

        public CustomNode(String id, String pid) {
            this.id = id;
            this.pid = pid;
        }
    }


    public List<String>  dfs(List<CustomNode> input){
        List<String> res = new ArrayList<>();
        Map<String,List<String>> map = new HashMap<>();
        String root = "";
        for (CustomNode customNode : input) {
            //对value进行操作：如果存在则获取value    不存在则设置value
            map.computeIfAbsent(customNode.pid, k -> new ArrayList<>()).add(customNode.id);
            if(customNode.pid.equals("-1")){
                root = customNode.id;
            }
        }
        if(root == ""){
            return res;
        }
        dfsImpl(map,root,"",res);
        return res;

    }

    public void dfsImpl(Map<String,List<String>> map,String cur,String pre,List<String> res){
        if(cur == null){
            return;
        }
        String target = pre+"/"+cur;
        res.add(target);
        List<String> sid = map.get(cur);
        if(sid != null){
            for (String s : sid) {
                dfsImpl(map,s,target,res);
            }
        }
    }
}
